package my;

import my.heap.BinaryHeap;
import my.printer.BinaryTrees;

/**
 * <p>
 * 测试
 * </p>
 *
 * @author AJun
 * @since 2020/9/6
 */
public class Main13 {

    public static void main(String[] args) {
        // test1();
        // test2();
        // test3();
        test4();
    }

    static void test4() {
        // TopK 问题
        // 新建一个小顶堆
        BinaryHeap<Integer> heap = new BinaryHeap<>((o1, o2) -> o2 - o1);

        // 从海量数据中找出最大的前 k 个数
        int k = 4;
        Integer[] data = {
                51, 30, 39, 92, 74, 25, 16, 93, 91,
                19, 54, 47, 73, 62, 76, 63, 35, 18,
                90, 6, 65, 49, 3, 26, 61, 21, 48
        };
        // 扫描这些数据，将遍历到的前 k 个数放到小顶堆中
        for (Integer ele : data) {
            if (heap.size() < k) { // 前k个数添加到小顶堆
                heap.add(ele); // logk
            } else if (ele > heap.get()) { // 如果是第 k + 1 个数，并且大于堆顶元素
                heap.replace(ele); // logk
            }
        }

        // O(nlogk)
        BinaryTrees.println(heap);
    }

    static void test3() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data, (o1, o2) -> o2 - o1); // 小顶堆
        BinaryTrees.println(heap);
    }

    static void test2() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data);
        // BinaryHeap<Integer> heap = new BinaryHeap<>(data, Integer::compareTo);
        BinaryTrees.println(heap);

        data[0] = 10;
        data[1] = 20;
        BinaryTrees.println(heap);
    }

    static void test1() {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(10);
        heap.add(90);
        heap.add(65);
        BinaryTrees.println(heap);

        // heap.remove();
        // BinaryTrees.println(heap);

        System.out.println(heap.replace(70));
        BinaryTrees.println(heap);
    }

}
